/**
 * Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6
The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6
 */
package com.xinpan.exercise;

public class FlattenBinaryTreeToLinkedList {
    public void flatten(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(root == null)
            return;
        
        TreeNode last = flat(root.left);
        if(last != null)
        {
            last.right = root.right;
            root.right = root.left;
            root.left = null;
            flat(last.right);
        }
        else
            flat(root.right);
    }
    
    public TreeNode flat(TreeNode root)
    {
        if(root == null)
            return null;
        

        TreeNode last = flat(root.left);
        TreeNode newLast = null;
        if(last != null)
        {
            last.right = root.right;
            root.right = root.left;
            root.left = null;
            newLast = flat(last.right);
        }
        else
        {
            last = flat(root.right);
        }
        if(newLast != null)
            return newLast;
        else if(last != null)
            return last;
        else
            return root;
    }
    
    class TreeNode {
    	      int val;
    	      TreeNode left;
    	      TreeNode right;
    	      TreeNode(int x) { val = x; }
    	  }
}
